/* Given an array of integers, return indices of the two numbers such that they add up to a specific target. */
/* You may assume that each input would have exactly one solution, and you may not use the same element twice. */
/* Example: */
/* Given nums = [2, 7, 11, 15], target = 9, */
/* Because nums[0] + nums[1] = 2 + 7 = 9, */
/* return [0, 1]. */
/* [解法]:hash表中寻找减数 */
#include <iostream>
#include "vector"
#include "math.h"
#include <unordered_map>
using namespace std;
class Solution 
{
public:
    vector<int> twoSum(vector<int> &numbers, int target)
    {
        // 使用哈希表存储数组中的数值，key为数组中的数值，value为数组中数值对应下标 
        unordered_map<int, int> hash;
        vector<int> result;
        for (int i = 0; i < numbers.size(); i++) 
        {
            int numberToFind = target - numbers[i];
    
            // 查找，若找到，则返回下标
            if (hash.find(numberToFind) != hash.end()) 
            {
                result.push_back(hash[numberToFind]);
                result.push_back(i);            
                return result;
            }
    
            //若没有找到，则将该值加入哈希表
            hash[numbers[i]] = i;
        }
        return result;
    }
};
